/*
 * @lc app=leetcode.cn id=46 lang=cpp
 *
 * [46] 全排列
 */
#include <vector>
using std::vector;
// @lc code=start
class Solution
{
  private:
    void permute_dfs(const vector<int> &nums, vector<int> &state, vector<bool> &visited, vector<vector<int>> &res)
    {
        if (nums.size() == state.size()) {
            res.push_back(state);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (!visited[i]) {
                visited[i] = true;
                state.push_back(nums[i]);
                permute_dfs(nums, state, visited, res);
                visited[i] = false;
                state.pop_back();
            }
        }
    }

  public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<bool> visited(nums.size(), false);
        vector<int> state;
        permute_dfs(nums, state, visited, res);
        return res;
    }
};
// @lc code=end
